const 
	MAXDIG = 170; 
	BASE : int64 = round(1e18);
	
type 
	TLong = array[0..MAXDIG] Of Int64;
	
var 
	a,b,c,d:TLong;
	s,t:string;

function StrToLong(s:string):TLong;

var 
	i,ls,j:longint;
	
begin
fillchar(result,sizeof(result),0);
s:=s+'$';
while s[1] = '0' do delete(s,1,1);
delete(s,length(s),1);
ls:=length(s);
if ls = 0 then begin
	s := s + '0';
	inc(ls);
end;
for j := 1 to ls do begin
	for i := result[0] downto 1 do begin
		result[i + 1] := result[i + 1] + (result[i] * 10) div BASE;
		result[i] := (result[i] * 10) mod BASE;
	end;
	result[1] := result[1] + ord(s[j]) - 48;
	if result[result[0] + 1] > 0 then inc(result[0]);
end;
end;

function LongToStr(a:TLong):string;
var
	i,lls:longint;
	ls,s:string;
	
begin
str(BASE div 10, ls);
lls := length(ls);
result := inttostr(a[a[0]]);
for i := a[0] - 1 downto 1 do begin
	str(a[i], s);
	while length(s) < lls do s := '0' + s;
	result := result + s;
end;
end;

function add(A, B : Tlong):TLong;

var
	i,k:longint;

begin
fillchar(result,sizeof(result),0);
if a[0] > b[0] then k := a[0] else k := b[0];
for i:=1 to k do begin
	result[i + 1] := (result[i] + a[i] + b[i]) Div BASE;
	result[i] := (result[i] + a[i] + b[i]) Mod BASE;
end;
if result[k + 1] = 0 then result[0] := k else result[0] := k + 1;
end;
	
function eq(a,b:TLong):boolean;

var
	i:longint;

begin
result:=false;
if a[0] <> b[0] then exit;
i := 1;
while (i <= a[0]) and (a[i] = b[i]) do inc(i);
result := i = a[0] + 1;
end;
	
function more(a,b:TLong):boolean;

var
	i:longint;

begin
if a[0] < b[0] then result := false else
if a[0] > b[0] then result := true else begin
	i := a[0];
	while (i > 0) and (a[i] = b[i]) do dec(i);
	result := (i <> 0) and (a[i] > b[i]);
end;
end;

function less(a,b:TLong):boolean;
begin
result := not(more(a,b) or eq(a,b));
end;
	
function more_eq(a,b:TLong):boolean;
begin
result := more(a, b) or eq(a,b);
end;
	
function less_eq(a,b:tlong):boolean;
begin
result := not more(a,b);
end;

function mul_short(a:TLong; k:int64):TLong;

var
	i:longint;

begin
fillchar(result,sizeof(result),0);
if k = 0 then result[0] := 0 else begin
	for i:=1 to a[0] do begin
		result[i + 1] := (a[i] * k + result[i]) div BASE;
		result[i] := (a[i] * k + result[i]) mod BASE;
	end;
	if result[a[0] + 1] > 0 then result[0] := a[0] + 1 else result[0] := a[0];
end;
end;

function sub(a,b:TLong; sp:longint):TLong;

var
	i,j:longint;
	
begin
for i:=1 to b[0] do begin
	dec(a[i + sp], b[i]);
	j := i;
	while (a[j + sp] < 0) and (j <= a[0]) do begin
		inc(a[j + sp], BASE) ;
		dec(a[j + sp + 1]); 
		inc(j);
	end;
end;
i := a[0];
while (i > 1) and (a[i] = 0) do dec(i);
a[0] := i;
result := a;
end;
	
function more_sdvig(a,b:TLong; sdvig:longint):byte;

var
	i:longint;
	
begin
if a[0] > b[0] + sdvig then result := 0 else
if a[0] < b[0] + sdvig then result := 1 else begin
	i := a[0];
	while (i > sdvig) and (a[i] = b[i - sdvig]) do dec(i);
	if i = sdvig then begin
		result := 0;
		for i:=1 to sdvig do
			if a[i] > 0 then exit;
		result := 2;
	end else result := byte(a[i] < b[i - sdvig])
end;
end;

function findbin(var ost:Tlong; b:TLong; sp:longint):longint;

Var 
	up,down,tmp:int64;
	c:TLong;

begin
up := BASE;
down := 0;
while up - down > 1 do begin
	tmp := (up + down) shr 1;
	c := mul_short(b, tmp);
	case more_sdvig(ost, c, sp) of
		0: down := tmp;
		1: up := tmp;
		2: begin 
			up := tmp; 
			down := tmp;
		end;
	end;	
end;
c := mul_short(b, (up + down) shr 1);
if more_sdvig(ost, c, 0) = 0 then ost := sub(ost, c, sp) else begin
	c := sub(c, ost, sp); 
	ost := c;
end;
result := (up + down) shr 1;
End;

procedure makedel(a,b:TLong; var res,ost:TLong);

var
	sp:longint;

begin
ost := a;
sp := a[0] - b[0];
if more_sdvig(a,b,sp) = 1 then dec(sp);
res[0] := sp + 1;
while sp >= 0 do begin
	res[sp + 1] := findbin(ost,b,sp);
	dec(sp);
end;
end;

procedure divide(a,b:TLong; var res,ost:TLong);
begin
fillchar(res,sizeof(res),0);
fillchar(ost,sizeof(ost),0);
res[0] := 1;
ost[0] := 1;
case more_sdvig(a,b,0) of
	0: makedel(a,b,res,ost);
	1: ost := a;
	2: res[1] := 1;
end;
end;

function mul(a,b:TLong):TLong;

var 
	cr,cc,carry,sum,dp,nr,nc:int64;
	s,t:string;
	row,col:TLong;
	i,j:longint;
	
begin
for i:=a[0] downto 1 do
	row[a[0] - i + 1] := a[i];
for i:=b[0] downto 1 do
	col[b[0] - i + 1] := b[i];
nr := a[0];
nc := b[0];
dp := high(row); 
cr := nr; 
cc := nc;
carry := 0;
while (cc > 0) do begin
	i := cr; 
	j := cc; 
	sum := carry;
	while (i <= nr) and (j >= 1) do begin
		inc(sum, row[i] * col[j]);
		inc(i); 
		dec(j);
	end;
	row[dp] := sum mod BASE; 
	dec(dp);
	carry := sum div BASE;
	if cr > 1 then dec(cr) else dec(cc);
end;
while (carry <> 0) do begin
	row[dp] := carry mod BASE;
	carry := carry div BASE;
	dec(dp);
end;
inc(dp);  
s:='';    
while (dp <= high(row)) do begin
	str(row[dp],t);
	s := s + t;
	inc(dp);
end;
result := strtolong(s);
end;